赛题背景
随着互联网移动支付的迅速普及，我们享受到越来越多的生活便利。如当您走入商场的某家餐厅时，手机会自动弹出该餐厅的优惠券；当您走入商场服装店时，手机可以自动推荐这家店里您喜欢的衣服；在您路过商场一家珠宝店时，手机可以自动提示您想了很久的一款钻戒已经有货了；离开商场停车场时，手机在您的许可下可以自动交停车费。这些您所享受的贴心服务都离不开背后大数据挖掘和机器学习的支持。在正确的时间、正确的地点给用户最有效的服务，是各大互联网公司智能化拓展的新战场。
赛题
对赛题提供的数据进行店铺、用户、WIFI等各个维度进行数据挖掘和特征创建，并自行创建训练数据中的负样本，进行合适的机器学习训练。测试数据中，根据当时用户所处的位置和WIFI等环境信息，通过算法或模型准确的判断出用户当前所在的店铺。
本次大赛我们将提供在2017年8月份大概100家商场（复赛为2017年7-8月大概500家商场）的详细数据，包括用户定位行为和商场内店铺等数据（已脱敏），参赛队伍需要对其进行数据挖掘和必要的机器学习训练。另外，我们会提供2017年9月份的商场内用户数据来做评测，检测您的算法是否能准确的识别出当时用户所在的店铺。
这是一个室内定位问题。给定交易时的环境信息(包括GPS、wifi信息)，确定交易所处的商铺。
数据
1、商场内店铺的信息数据，这个对训练和评测都是统一的。
2、真实用户在这些商场内的一段时间的到店交易数据，训练和评测将采用不同的时间段。
本赛题采用准确率进行评价。详细评分算法如下：
预测正确：您给出的shop_id和标准答案的shop_id相等。
Table 1、店铺和商场信息表
| Field | Type | Description | Note |
|---|---|---|---|
| shop_id | String | 店铺ID | 已脱敏 |
| category_id | String | 店铺类型ID | 共40种左右类型，已脱敏 |
| longitude | Double | 店铺位置-经度 | 已脱敏，但相对距离依然可信 |
| latitude | Double | 店铺位置-纬度 | 已脱敏，但相对距离依然可信 |
| price | Bigint | 人均消费指数 | 从人均消费额脱敏而来，越高表示本店的人均消费额越高 |
| mall_id | String | 店铺所在商场ID | 已脱敏 |
Table 2、用户在店铺内交易表
| Field | Type | Description | Note | ||||||
|---|---|---|---|---|---|---|---|---|---|
| user_id | String | 用户ID | 已脱敏 | ||||||
| shop_id | String | 用户所在店铺ID | 已脱敏。这里是用户当前所在的店铺，可以做训练的正样本。（此商场的所有其他店铺可以作为训练的负样本） | ||||||
| time_stamp | String | 行为时间戳 | 粒度为10分钟级别。例如：2017-08-06 21:20 | ||||||
| longitude | Double | 行为发生时位置-经度 | 已脱敏，但相对距离依然可信 | ||||||
| latitude | Double | 行为发生时位置-纬度 | 已脱敏，但相对距离依然可信 | ||||||
| wifi_infos | String | 行为发生时Wifi环境，包括bssid（wifi唯一识别码），signal（强度），flag（是否连接） | 例子：b_6396480\ | -67\ | false;b_41124514\ | -86\ | false;b_28723327\ | -90\ | false;解释：以分号隔开的WIFI列表。对每个WIFI数据包含三项：b_6396480是脱敏后的bssid，-67是signal强度，数值越大表示信号越强，false表示当前用户没有连接此WIFI（true表示连接）。 |
Table 3、评测集
| Field | Type | Description | Note |
|---|---|---|---|
| row_id | String | 测试数据ID | |
| user_id | String | 用户ID | 已脱敏，并和训练数据保持一致 |
| mall_id | String | 商场ID | 已脱敏，并和训练数据保持一致 |
| time_stamp | String | 行为时间戳 | 粒度为10分钟级别。例如：2017-08-06 21:20 |
| longitude | Double | 行为发生时位置-经度 | 已脱敏，但相对距离依然可信 |
| latitude | Double | 行为发生时位置-纬度 | 已脱敏，但相对距离依然可信 |
| wifi_infos | String | 行为发生时Wifi环境，包括bssid（wifi唯一识别码），signal（强度），flag（是否连接） | 格式和训练数据中wifi_infos格式相同 |
结果
| Field | Type | Description | Note |
|---|---|---|---|
| row_id | String | 测试数据ID | 下载的测试文件中的row_id |
| shop_id | String | 店铺ID | 算法检测的结果 |
解题分析
数据分析
- 某个同学对于某个 mall 坐标的可视化结果，黑色的是 shop 实际坐标，同色的是同一个shop的，可见其坐标偏离很大。
- 公共WIFI，存在类似 cmcc 等公共 wifi 的强度干扰，需要剔除
- wifi 出现次数过少，或者 null 的填充平均
- WiFi 信号强度转换 信号强度 = (strength + 113)/2
解题方案
二分类方案
即针对测试集中的每一条记录，构造候选shop集合，用模型输出每个候选的概率值，然后选取概率值最大的作为该条记录的预测shop。训练集和测试集的构造方法图示如下：
| 特征 | 时间 |
|---|---|
| 训练集-特征提取区间 | 7.1 - 8.24 |
| 训练集 | 8.25 - 8.31 |
| 线上测试集-特征提取区间 | 7.1- 8.31 |
| 线上测试集 | 9.1 - 9.14 |
| 本地训练区间 | 8.18-8.24 |
| 本地验证区间 | 8.25-8.31 |
训练：
| row_id | 候选 | 特征 | label |
|---|---|---|---|
| 1 | shop_1 | … | 1 |
| 1 | shop_2 | … | 0 |
| 1 | shop_3 | … | 0 |
| 2 | shop_1 | … | 0 |
| 2 | shop_2 | … | 1 |
| 2 | shop_3 | … | 0 |
测试：
| row_id | 候选 | 特征 | 输出概率 | 预测 |
|---|---|---|---|---|
| 3 | shop_1 | … | 0.6 | |
| 3 | shop_2 | … | 0.8 | |
| 3 | shop_3 | … | 0.9 | √ |
| 4 | shop_1 | … | 0.1 | |
| 4 | shop_2 | … | 0.9 | √ |
| 4 | shop_3 | … | 0.2 |
建立候选集
二分类思路需要构造候选集，相当于不知道正样本的情况下去构造可能的解。我们使用当前最强的前几个 WIFI，所对应的历史出现过最强的几个WIFI 信号所在的几个 shop 作为候选集，实际强度选定需要测试覆盖率，也就是选的候选在训练集中是否出现了，覆盖率了决定了模型上限，因为测试集中如果没有覆盖到真正的值，则怎么选都是失败的。我们的候选策略做的不够。（最后线下覆盖率 98% 正负比例 1：15）
- 在特征区间F中，找出wifi的最大信号强度Wmax以及wifi-shop的“一对多”关系relation
- 针对样本区间D中每一条样本的所有wifi，逐一比较当前wifi的信号强度与特征区间F中的Wmax的差值
- 若差值在7.5之内，选取relation中的shop作为候选shop
- 对上述规则方法没有覆盖到的样本，采用mall中全体shop作为候选shop，最后进行去重
以下是其它队伍候选策略：
- 全量做候选
- wifi 计数top历史
- GeoKNN聚类
- 用户在此商场去过的商店次数最多的n个。
- Cos 相似度
- LCS 公共序列
- 用户访问过的商店
- 训练集保留全部正样本，负样本随机抽样（训练时好）
特征
\1. user 特征
- user在候选shop的消费次数
- user在候选shop所属类型category的消费次数
- user历史平均price/候选shop的price
\2. WiFi 特征
- wifi是否连接
- wifi当前信号强度/wifi历史平均信号强度
\3. shop 特征
- 候选shop的ID
- 候选shop的price
- 候选shop总人流量/该mall总人流量
- 候选shop每小时人流量/该mall每小时人流量
- 候选shop每时段人流量/该mall每时段人流量
- 候选shop类型category的总人流量/该mall总人流量
- 候选shop类型category的每小时人流量/该mall每小时人流量
- 候选shop类型category的每时段人流量/该mall每时段人流量
- 候选shop被连接次数/候选shop总人流量
\4. shop-wifi特征
(1)shop-单wifi特征
- 候选shop_wifi平均信号强度
- 候选shop_wifi的信号强度方差
- 候选shop_wifi的出现次数/候选shop总人流量
- 候选shop_wifi的连接次数/候选shop连接次数
- wifi当前信号强度/候选shop平均信号强度
- wifi当前信号强度/候选shop_wifi平均信号强度
- 候选shop_wifi平均信号强度/候选shop平均信号强度
(2)shop-wifi1-wifi2联合特征
- 候选shop历史记录中wifi1信号强度 + wifi2信号强度的平均值，最大值，最小值
- 候选shop历史记录中wifi1信号强度 - wifi2信号强度的平均值，最大值，最小值
- 当前记录wifi1信号强度 + wifi2信号强度
- 当前记录wifi1信号强度 - wifi2信号强度
- 候选shop_wifi1_wifi2的出现次数/候选shop总人流量
- 候选shop_wifi1_wifi2的连接次数/候选shop连接次数
\5. GPS特征
- 当前记录user的经纬度、候选shop的经纬度
- 当前记录user经纬度与候选shop经纬度的距离及方向角
- 当前记录user经纬度与候选shop历史记录user经纬度的距离及方向角的最大值、最小值、平均值、中位数
- 候选shop经纬度与候选shop历史记录user经纬度的距离及方向角的中位数
- 预估wifi位置（历史记录经纬度平均值、中位数）与候选shop经纬度的距离及方向角
\6. Rank特征
- user在候选shop的消费次数的排序
- user在候选shop所属类型category的消费次数的排序
- 当前记录user经纬度与候选shop经纬度的距离的排序
- 当前记录user经纬度与候选shop历史记录user经纬度的距离的最大值、最小值、平均值、中位数的排序
- 候选shop经纬度与候选shop历史记录user经纬度的距离的中位数的排序
- 预估wifi位置（历史记录经纬度平均值、中位数）与候选shop经纬度的距离的排序
模型融合
不同模型加权融合的结果作为最终结果。
复赛中，考虑一个 wifi 的情况单独训练
第一名的队伍将多个算法的输出结果放入二分类模型中一起训练，提升准确率，值得学习。
多分类
多分类是比赛初期比较容易想到的方案，需要对每个 mall 进行多分类训练，类别数即为 mall 中 shop 的数目。将经纬度和每一个出现过的 wifi 强度都作为特征。比赛中有位同学已经开源了多分类的方案，代码也很简洁。多分类在线上平台赛的时候，需要分别计算四五百个 mall 很不方便，很可惜我们队伍没有使用多分类的方案融合进模型里，第一名使用多分类的输出概率作为二分类的输出特征，这一部分加分很多。
缺点：单个模型样本不多，特征稀疏，模型精度不高，没法去挖掘店铺相关特征，或者用户与店铺交互特征（测试集中没有，没有候选）
优点：样本召回率高，与二分类具有一定互补性。
收获总结
这是第一次参加数据挖掘类的比赛，有幸和队友一起直接打到决赛并拿到TOP2，是一段非常有意义的经历。二分类的思想去解决这样的问题是我之前没有碰到过的。在平台赛的过程中阅读了阿里云 MaxCompute 的文档，搭建开发环境，开发 Mapreduce 以及 Hive UDF ，对于大数据工具与机器学习的结合了解更深。此外，解题过程还可以推荐的角度来思考，用户可能在其所喜爱的店铺打开支付宝，加入推进系统相关特征，可惜没有实现。需要多从业务场景出发，思考特征工程。
部分开源资料：
- 第一名：https://github.com/drop-out/Tianchi-Wifi-Positioning?spm=5176.9876270.0.0.614ee44a8ET8Cu
- B榜 199 ：https://github.com/ylhao/TIANCHI?spm=5176.9876270.0.0.2687e44a61CcJi
- 15 名：https://github.com/InsaneLife/Positioning-shops
- 第七名 加入 lambdarank：https://github.com/totoruo/TianChi-Shop-Location-Competition
- QGIS用于数据竞赛的简单地理可视化：https://www.jianshu.com/p/25ae219369b8?spm=5176.9876270.0.0.7f03e44aOtB1HS&utm_campaign=hugo&utm_medium=reader_share&utm_content=note&utm_source=qq